package com.gjx.leetcode;

//16. 最接近的三数之和
//
//给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
//
//例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
//
//与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

public class Solution016 {
	public int threeSumClosest(int[] nums, int target) {
        
		sort(nums, new int[nums.length], 0, nums.length-1);
		
		int ans = Integer.MAX_VALUE;
		int diff = Integer.MAX_VALUE;
		
		for (int i=0; i<nums.length-2; i++) {
			if (i > 0 && nums[i] == nums[i-1]) {
				continue;
			}
			
			int left = i + 1;
			int right = nums.length - 1;
			
			while (left < right) {
				
				int sum = nums[left] + nums[right];
				
				if (sum + nums[i] == target) {
					return target;
				} else if (sum + nums[i] > target) {
					right--;
					
					if (sum + nums[i] - target < diff) {
						diff = sum + nums[i] - target;
						ans = sum + nums[i];
					}
					
				} else {
					left++;
					
					if (target - sum - nums[i] < diff) {
						diff = target - sum - nums[i];
						ans = sum + nums[i];
					}
				}
				
			}
			
		}
		
		return ans;
    }
	
	
	private void sort(int[] nums, int[] temp, int lo, int hi) {
		if (lo >= hi) {
			return;
		}
		int mid = lo + (hi - lo) / 2;
		
		sort(nums, temp, lo, mid);
		sort(nums, temp, mid+1, hi);
		merge(nums, temp, lo, mid, hi);
	}
	
	private void merge(int[] nums, int[] temp, int lo, int mid, int hi) {
		
		for (int i=lo; i<=hi; i++) {
			temp[i] = nums[i];
		}
		
		int i=lo;
		int j=mid+1;
		
		int k=lo;
		
		while (k <= hi) {
			
			if (i > mid) {
				nums[k++] = temp[j++];
			} else if (j > hi) {
				nums[k++] = temp[i++];
			} else if (temp[i] < temp[j]) {
				nums[k++] = temp[i++];
			} else {
				nums[k++] = temp[j++];
			}
			
		}
		
	}
	
	public static void main(String[] args) {
		new Solution016().threeSumClosest(new int[]{-1, 2, 1, -4}, 1);
	}
	
}
